//
// Created by Vincent_Vic on 2020/4/15.
//

#ifndef DATAORGANIZATION_HUFFMAN_H
#define DATAORGANIZATION_HUFFMAN_H
#include<queue>
#include <string>

using namespace std;

class Huffman {
private:
    struct Node{
        int weight;
        string data;
        Node* left;
        Node* right;
        Node(int weight){
            this->weight = weight;
        }

        Node(int weight, const string data) : weight(weight), data(data) {}

        Node(int weight, Node *left, Node *right) : weight(weight),  left(left), right(right) {}

        bool operator <(Node a) const  {  return weight < a.weight; }
        bool operator >(Node a) const  {  return weight > a.weight; }
    };
    static const int LEN = 256;
    string charCode[LEN];
    unsigned char* weights;
    Node* root;
public:

    //创建哈夫曼
    void createHufman( unsigned char *weights,int size){
        //优先队列
        priority_queue<Node*,vector<Node*>,greater<Node>> nodes;
        for (int i =0 ; i< size;i++) {
            nodes.push(new Node(weights[i],i+""));
        }

        while (nodes.size() > 1){
            Node* m1 = nodes.top();
            nodes.pop();
            Node* m2 = nodes.top();
            nodes.pop();

            Node* parent = new Node(m1->weight+m2->weight,m1,m2);
            nodes.push(parent);
        }
        root = nodes.top();
    }

    // 生成哈夫曼编码
    void generateCode(Node* root, string s) {
        // 叶子节点
        if (root->left == nullptr && root->right == nullptr) {
            // 保存至编码数组对应位置
            charCode[(int) root->data[0]] = s;
        }
        // 左边加0
        if (root->left != nullptr) {
            generateCode(root->left, s + "0");
        }
        // 右边加1
        if (root->right != nullptr) {
            generateCode(root->right, s + "1");
        }
    }


};


#endif //DATAORGANIZATION_HUFFMAN_H
